#include <iostream>
#include <sstream>
#include <string>
#include <fstream>
#include <stdlib.h>
#include <time.h>

using namespace std;

string caminho_entrada; // Caminho do arquivo de entrada definido no config.ini
string Nome_Matriz;
int linhas; // Numero de linhas da matriz conforme arquivo de entrada
int colunas; // Numero de colunas da matriz conforme arquivo de entrada
int max_clusters; // Numero maximo de clusters
int tamanho_vizinhanca; // Tamanho da vizinhaca definida com base nas estruturas de vizinhancas selecionadas no config.ini
int Total_Repeticoes;
int nbmax;
int TamanhoTabu;
ofstream Saida_Parcial;
ofstream Saida_Final;
ofstream Saida_Repeticao;

struct Tabu{
	int DeLinha;
	int ParaLinha;
	int DeColuna;
	int ParaColuna;
};

struct Vizinhanca{
	int *Solucao;
	float FO;
	char **Matriz;
	Tabu Movimento;
};


void carregar_configuracao();
char ** carregar_entrada();
void tabu(char **M, int repeticao_atual);
int * gerar_solucao_inicial(int cluster);
int gerar_aleatorio(int Max);
Vizinhanca * gerar_solucoes_vizinhas(int *s, int clusters, char ** M);
Vizinhanca get_Vizinho(int *s, int clusters, char **M, int deL, int paraL, int deC, int paraC);
char ** copiar_matriz(char **s);
int * copiar_solucao(int *s);
void imprimir_matriz(char **m);
char * copiar_linha(char *l);
char ** trocar_colunas(char **s, int c1, int c2);
float calcular_FO(int *sol, int clusters, char **m);
bool IsTabu(Vizinhanca V, Tabu* Lista);
Tabu * AtualizarListTabu(Tabu* Lista, Tabu Movimento);

int main(){
	char **M;
	int i, x;

	// TODO - Inicializa o gerador de numeros aleatorios - descomentar essa linha
    srand((unsigned)time(NULL));

	//criar funcao para ler o arquivo de configuracao e carregar dados de inicializacao
	carregar_configuracao();

	//carregar arquivo de entrada
	M = carregar_entrada();

	TamanhoTabu = 10;

	// TODO - Definir o tamnho da vizinhanca
	max_clusters = linhas / 2;
	if(colunas > linhas)
		max_clusters = colunas / 2;

	Saida_Parcial.open("Saida_Parcial.txt");
	Saida_Parcial << "Iteracao;Melhor_Global" << endl;
	Saida_Repeticao.open("Saida_Repeticao.txt");
	Saida_Repeticao << "Iteracao;Melhor_Global" << endl;
	Saida_Final.open("Saida_Final.txt");

	for(i = 1; i <= Total_Repeticoes; i++){
		//chamar funcao
		tabu(M, i);
	}
	Saida_Parcial.close();
}


void carregar_configuracao(){
  string line;
  string aux;
  ifstream myfile ("config.ini"); // ifstream = padrão ios:in
  if (myfile.is_open())
  {
    while (! myfile.eof() ) //enquanto end of file for false continua
    {
      getline (myfile,line); // como foi aberto em modo texto(padrão)
                             //e não binário(ios::bin) pega cada linha
      if(line.find("=") <= line.size()){
    	  aux = line.substr(0,line.find("="));
    	  //cout << line << " - " << aux << " - " << line.substr(line.find("=")+1) << endl;
    	  if(aux == "[caminho entrada]")
    		  caminho_entrada = line.substr(line.find("=")+1);
    	  else if(aux == "[nbmax]")
			  istringstream(line.substr(line.find("=")+1)) >> nbmax;
    	  else if(aux == "[repeticoes]")
    		  istringstream(line.substr(line.find("=")+1)) >> Total_Repeticoes;
    	  else if(aux == "[tamanho tabu]")
    		  istringstream(line.substr(line.find("=")+1)) >> TamanhoTabu;
    	  else if(aux == "[tamanho vizinhanca]")
    		  istringstream(line.substr(line.find("=")+1)) >> tamanho_vizinhanca;
      }
    }
    myfile.close();
  }
  else cout << "Falha ao abrir config.ini" << endl;
}

char ** carregar_entrada(){
	string line;
	string aux;
	string sep;
	int i, l = 0, c;
	char **M;

	ifstream myfile (caminho_entrada.c_str()); //c_str converte tipo string da classe para o tipo string do C (utilizado pelo ifstream)
	if (myfile.is_open())
	{
		while (!myfile.eof() ) //enquanto end of file for false continua
		{
			getline (myfile,line); // como foi aberto em modo texto(padrão)
								   //e não binário(ios::bin) pega cada linha


			if(line.find("=") <= line.size()){ // Le a primeira linha da matriz e cria conforme o tamanho especificado
				aux = line.substr(line.find("=")+1);
				if(aux.find("x") <= aux.size()){
					istringstream(aux.substr(0, aux.find("x"))) >> linhas;
					istringstream(aux.substr(aux.find("x")+1)) >> colunas;
					//cout << "Criando matriz" << endl;

					M = (char **) calloc (linhas, sizeof(char *));

					/* aloca as colunas da matriz*/
					for (i = 0; i < linhas; i++ ) {
						M[i] = (char *) calloc (colunas, sizeof(char));
					}


				}
			}
			else{ //Carrega a matriz com base nos valores de entrada
				for(i = 0; i < line.size(); i++){
					M[l][i] = line.at(i);
				}
				l++;
			}
		}

/*		cout << "Imprimindo a matriz de entrada - TROCA LINHAS" << endl;
		for (i=0;i<linhas;i++){
			for(int j=0;j<colunas;j++)
				cout << M[i][j] << " ";
			cout << endl;
		}
*/
		myfile.close();
	}
	else cout << "Falha ao abrir arquivo de entrada: " << caminho_entrada << endl;

	return M;
}

void tabu(char **M, int repeticao_atual){
	int * S; // Solucao atual
	Vizinhanca *V, Melhor_Atual, Melhor_Global; // Solucoes vizinhas
	int count = 0, i, it = 0;
	float FO;
	int numero_clusters = 2;

	/*	cout << "Imprimindo a matriz INICIAL" << endl;
	for (int i=0;i<linhas;i++){
		for(int j=0;j<colunas;j++)
			cout << M[i][j] << " ";
		cout << endl;
	}
*/
	S = gerar_solucao_inicial(numero_clusters);

	Melhor_Atual = get_Vizinho(S, 2, M, 0, 0, 0, 0);
	Melhor_Global = get_Vizinho(S, 2, M, 0, 0, 0, 0);

	Tabu * ListaTabu = (Tabu *) calloc (TamanhoTabu, sizeof(Tabu));

	// Gera solucao incial aleatoriamente
	for(numero_clusters = 2; numero_clusters <= max_clusters; numero_clusters++){

		//cout << "Gerando solucao inicial - " << numero_clusters << endl;
		if(numero_clusters > 2){
			S = gerar_solucao_inicial(numero_clusters);
			Vizinhanca aux = get_Vizinho(S, 2, M, 0, 0, 0, 0);
			if (Melhor_Global.FO < aux.FO)
				Melhor_Global = aux;
			Melhor_Atual = aux;
		}
		cout << "Clusters " << numero_clusters << endl;
		for(i = 0; i < linhas + colunas; i++){
			cout << S[i] << " ";
		}
		cout << endl;

		//cout << "CRIANDO LISTA TABU" << endl;
		for(i = 0;i < TamanhoTabu; i++){
			ListaTabu[i].DeLinha = 0;
			ListaTabu[i].ParaLinha = 0;
			ListaTabu[i].DeColuna = 0;
			ListaTabu[i].ParaColuna = 0;
		}

		// Criterio de parada
		while(count <= nbmax){
			//Gerar solucoes vizinhas
			//cout << "Gerando solucao vizinha" << endl;
			V = gerar_solucoes_vizinhas(Melhor_Atual.Solucao, numero_clusters, M);

			//cout << "FIM DAS GERAÇÕES VIZINHAS" << endl;

			for(i = 1; i < tamanho_vizinhanca; i++){

				if(V[i].FO > Melhor_Atual.FO){
					if(IsTabu(V[i], ListaTabu)){
						if(V[i].FO > Melhor_Global.FO){
							Melhor_Atual = V[i];
							ListaTabu = AtualizarListTabu(ListaTabu, V[i].Movimento);
						}
					}else{
						Melhor_Atual = V[i];
						ListaTabu = AtualizarListTabu(ListaTabu, V[i].Movimento);
					}
				}
			}
			count++;
			if(Melhor_Atual.FO > Melhor_Global.FO){
				Melhor_Global = Melhor_Atual;
				count = 0;
			}
			it++;
			Saida_Parcial << it << ";" << Melhor_Atual.FO << ";" << Melhor_Global.FO << endl;
		}
	}
	Saida_Repeticao << repeticao_atual << ";" << Melhor_Global.FO << endl;

	Saida_Final << "Solucao" << endl;
	for(i = 0; i < linhas+colunas; i++)
		Saida_Final << Melhor_Global.Solucao[i] << ";";


	Saida_Final << endl << "Matriz" << endl;
	for(i = 0; i < linhas; i++){
		for(int j = 0; j < colunas; j++){
			Saida_Final << Melhor_Global.Matriz[i][j] << ";";
		}
		Saida_Final << endl;
	}
}

int * gerar_solucao_inicial(int cluster){
	int i;
	int * si = (int *) calloc(linhas + colunas, sizeof(int));

	for (i = 0; i < (linhas + colunas); i++)
		si[i] = gerar_aleatorio(cluster);

/*	cout << "Imprimindo solucao inicial" << endl;
	for(int i = 0; i <= (linhas + colunas); i++)
		cout << si[i] << " - ";
	cout << endl;
*/
	return si;
}

int gerar_aleatorio(int Max){
	return rand() % Max;
}


Vizinhanca * gerar_solucoes_vizinhas(int *s, int clusters, char ** M){
	Vizinhanca * V;
	int * s_aux;
	int v_atual = 0; // Solucao vizinha atual
	int l1, l2, c1, c2, i, iVizinho, vl, vc; //Linhas e colunas aleatorias a serem selecionadas
	char linha_aux;
	char coluna_aux;

	//cout << "Criando solucao vizinha" << endl;
	V = (Vizinhanca *) calloc (tamanho_vizinhanca, sizeof(Vizinhanca));

	/*
	 * V1 - Seleciona duas linhas aleatórias e troca elas
	 */
	for(iVizinho = 0; iVizinho < tamanho_vizinhanca/7; iVizinho++){
		//cout << "GERANDO VIZINHO " << iVizinho << endl;
		//cout << "Copiando solucao atual - V1" << endl;
		s_aux = copiar_solucao(s); // Inicializa a solucao

/*		cout << "Imprimindo solucao" << endl;
		for(i = 0; i <= (linhas + colunas); i++)
			cout << s_aux[i] << " - ";
		cout << endl;
*/
//		cout << "Gerando solucao vizinha" << endl;
		//Seleciona duas linhas diferentes aleatoriamente
		l1 = gerar_aleatorio(linhas);
		l2 = gerar_aleatorio(linhas);
		while(l1 == l2)
			l2 = gerar_aleatorio(linhas);

		linha_aux = s_aux[l1];
		s_aux[l1] = s_aux[l2];
		s_aux[l2] = linha_aux;

		V[iVizinho] = get_Vizinho(s_aux, clusters, M, l1, l2, 0, 0);

/*		s_aux = V[iVizinho].Solucao;

		cout << "Imprimindo solucao vizinha: " << l1 << " - " << l2 << endl;
		for(i = 0; i <= (linhas + colunas); i++)
			cout << s_aux[i] << " - ";
		cout << endl;

		cout << "Imprimindo matriz alterada" << endl;
		imprimir_matriz(V[iVizinho].Matriz);
		*/
	}

	/*
	 * V2 - Seleciona duas colunas aleatórias e troca elas    -    sigmaplot
	 */
	for(iVizinho = tamanho_vizinhanca/7; iVizinho < tamanho_vizinhanca/7*2; iVizinho++){
//		cout << "GERANDO VIZINHO " << iVizinho << endl;
//		cout << "Copiando solucao atual - V2" << endl;
		s_aux = copiar_solucao(s); // Inicializa a solucao
		v_atual = 1;

		//Seleciona duas linhas diferentes aleatoriamente
		c1 = gerar_aleatorio(colunas);
		c2 = gerar_aleatorio(colunas);
		while(c1 == c2)
			c2 = gerar_aleatorio(colunas);

//		cout << "V2 - " << c1 << " > " << c2 << endl;

		c1 = c1 + (linhas);
		c2 = c2 + (linhas);
		coluna_aux = s_aux[c1];
		s_aux[c1] = s_aux[c2];
		s_aux[c2] = coluna_aux;

		V[iVizinho] = get_Vizinho(s_aux, clusters, M, 0, 0, c1, c2);

/*		s_aux = V[iVizinho].Solucao;

		cout << "Imprimindo solucao vizinha: " << l1 << " - " << l2 << endl;
		for(i = 0; i < (linhas + colunas); i++)
			cout << s_aux[i] << " - ";
		cout << endl;

		cout << "Imprimindo matriz alterada" << endl;
		imprimir_matriz(V[iVizinho].Matriz);
		*/
	}
	/*
	 * V3 - Seleciona duas linhas e duas colunas aleatórias e troca elas    -    sigmaplot
	 */
	for(iVizinho = tamanho_vizinhanca/7*2; iVizinho < tamanho_vizinhanca/7*3; iVizinho++){
		s_aux = copiar_solucao(s); // Inicializa a solucao

		//Seleciona duas linhas diferentes aleatoriamente
		l1 = gerar_aleatorio(linhas);
		l2 = gerar_aleatorio(linhas);
		while(l1 == l2)
			l2 = gerar_aleatorio(linhas);

		linha_aux = s_aux[l1];
		s_aux[l1] = s_aux[l2];
		s_aux[l2] = linha_aux;

		//Seleciona duas colunas diferntes aleatoriamente
		c1 = gerar_aleatorio(colunas);
		c2 = gerar_aleatorio(colunas);
		while(c1 == c2)
			c2 = gerar_aleatorio(colunas);

		c1 = c1 + (linhas);
		c2 = c2 + (linhas);
		coluna_aux = s_aux[c1];
		s_aux[c1] = s_aux[c2];
		s_aux[c2] = coluna_aux;

		V[iVizinho] = get_Vizinho(s_aux, clusters, M, l1, l2, c1, c2);

	}

	/*
	 * V4 - Seleciona duas linhas e duas colunas aleatórias e troca elas    -    sigmaplot
	 */
	for(iVizinho = tamanho_vizinhanca/7*3; iVizinho < tamanho_vizinhanca/7*4; iVizinho++){
		s_aux = copiar_solucao(s); // Inicializa a solucao

		//Seleciona duas linhas diferentes aleatoriamente
		l1 = gerar_aleatorio(linhas);
		l2 = gerar_aleatorio(linhas);
		while(l1 == l2)
			l2 = gerar_aleatorio(linhas);

		linha_aux = s_aux[l1];
		s_aux[l1] = s_aux[l2];
		s_aux[l2] = linha_aux;

		//Seleciona duas colunas diferntes aleatoriamente
		c1 = gerar_aleatorio(colunas);
		c2 = gerar_aleatorio(colunas);
		while(c1 == c2)
			c2 = gerar_aleatorio(colunas);

		c1 = c1 + (linhas);
		c2 = c2 + (linhas);
		coluna_aux = s_aux[c1];
		s_aux[c1] = s_aux[c2];
		s_aux[c2] = coluna_aux;

		V[iVizinho] = get_Vizinho(s_aux, clusters, M, l1, l2, c1, c2);
	}
	/*
	 * V4 - Troca o valor de uma linha por outro valor aleatorio    -    sigmaplot
	 */
	for(iVizinho = tamanho_vizinhanca/7*4; iVizinho < tamanho_vizinhanca/7*5; iVizinho++){
		s_aux = copiar_solucao(s); // Inicializa a solucao

		//Seleciona uma linha
		l1 = gerar_aleatorio(linhas);
		//Gerar um novo valor aleatorio
		vl = gerar_aleatorio(clusters);
		while(l1 == vl)
			vl = gerar_aleatorio(clusters);

		s_aux[l1] = vl;

		V[iVizinho] = get_Vizinho(s_aux, clusters, M, l1, l2, c1, c2);
	}
	/*
	 * V5 - Troca o valor de uma coluna por outro valor aleatorio    -    sigmaplot
	 */
	for(iVizinho = tamanho_vizinhanca/7*5; iVizinho < tamanho_vizinhanca/7*6; iVizinho++){
		s_aux = copiar_solucao(s); // Inicializa a solucao

		//Seleciona uma coluna
		c1 = gerar_aleatorio(colunas);
		c1 = c1 + (linhas);

		//Gerar um novo valor aleatorio
		vc = gerar_aleatorio(clusters);
		while(c1 == vc)
			vc = gerar_aleatorio(clusters);

		s_aux[c1] = vc;

		V[iVizinho] = get_Vizinho(s_aux, clusters, M, l1, l2, c1, c2);
	}
	/*
	 * V6 - Troca o valor de uma linha e de uma coluna por outro valor aleatorio    -    sigmaplot
	 */
	for(iVizinho = tamanho_vizinhanca/7*6; iVizinho < tamanho_vizinhanca; iVizinho++){
		s_aux = copiar_solucao(s); // Inicializa a solucao

		//Seleciona uma linha
		l1 = gerar_aleatorio(linhas);
		//Gerar um novo valor aleatorio
		vl = gerar_aleatorio(clusters);
		while(l1 == vl)
			vl = gerar_aleatorio(clusters);

		s_aux[l1] = vl;

		//Seleciona uma coluna
		c1 = gerar_aleatorio(colunas);
		c1 = c1 + (linhas);

		//Gerar um novo valor aleatorio
		vc = gerar_aleatorio(clusters);
		while(c1 == vc)
			vc = gerar_aleatorio(clusters);

		s_aux[c1] = vc;

		V[iVizinho] = get_Vizinho(s_aux, clusters, M, l1, l2, c1, c2);
	}



	return V;
}

float calcular_FO(int *sol, int clusters, char **m){
	//calcular quantos 1s tem ao todo
	float total = 0, dentro = 0, fora = 0, vazio = 0, FO;
	int i, j, cluster;

	for(i = 0; i < linhas; i++){
		for(j = 0; j < colunas; j++){
			if(m[i][j] == '1')
				total++;
		}
	}

	for(i = 0; i < linhas; i++){
		for(j = 0; j < colunas; j++){
			if(m[i][j] == '1'){
				if(sol[i] == sol[linhas+j]){
					dentro++;
				}else{
					fora++;
				}
			}else{
				if(sol[i] == sol[linhas+j]){
					vazio++;
				}
			}
		}
	}

	FO = (total - fora) / (total + vazio);

//	cout << "Total " << total << " Dentro " << dentro << " Fora " << fora << " Vazio " << vazio << " FO " << FO << endl;

	return FO;

}

int * copiar_solucao(int *s){
	int * aux = (int *) calloc (linhas + colunas, sizeof(int));
	int i;
	for (i=0;i<linhas;i++)
		aux[i] = s[i];

	for (i=linhas;i<linhas+colunas;i++)
		aux[i] = s[i];
	return aux;
}

Vizinhanca get_Vizinho(int *s, int clusters, char **M, int deL, int paraL, int deC, int paraC){
	int cluster_atual, i, j, linha_atual = 0, coluna_atual = 0, troca, coluna, k;
	char **aux = copiar_matriz(M);
	char **nova;
	int *s_aux = copiar_solucao(s);
	Vizinhanca V;

	nova = (char **) calloc (linhas, sizeof(char *));
	for (i = 0; i < linhas; i++ )
		nova[i] = (char *) calloc (colunas, sizeof(char));

//	cout << "Ordenando a matriz" << endl;
//	cout << "Ordenando LINHAS" << endl;

/*	cout << "Imprimindo a matriz de parcial" << endl;
	for (i=0;i<linhas;i++){
		for(j=0;j<colunas;j++)
			cout << M[i][j] << " ";
		cout << endl;
	}

	cout << "NOVA" << endl;
*/
	//Ordernar as linhas conforme os valores dos clusters
	for (cluster_atual = 0; cluster_atual <= clusters; cluster_atual ++){
		//Altera a ordem das linhas
		for (i = 0; i < linhas; i++){
			if(s[i] == cluster_atual){

				nova[linha_atual] = copiar_linha(aux[i]);
				s_aux[linha_atual] = cluster_atual;

				linha_atual++;
			}
		}
	}

/*	cout << "Imprimindo a matriz de parcial" << endl;
	for (i=0;i<linhas;i++){
		for(j=0;j<colunas;j++)
			cout << nova[i][j] << " ";
		cout << endl;
	}
	cout << "Ordenando COLUNAS" << endl;
	for(j=0;j<linhas+colunas;j++)
		cout << s_aux[j] << " ";
	cout << endl;
*/


	//Ordernar as colunas conforme os valores dos clusters
	for (cluster_atual = 0; cluster_atual <= clusters; cluster_atual ++){
		//Altera a ordem das linhas
		for (i = linhas; i < linhas+colunas; i++){
			if(s_aux[i] == cluster_atual){
				//trocar coluna_atual com a coluna i
				coluna = i-linhas;
//				cout << "C_Atual " << coluna_atual << "  Col " << coluna << endl;

				for (j=0;j<linhas;j++){
					troca = nova[j][coluna];
					nova[j][coluna] = nova[j][coluna_atual];
					nova[j][coluna_atual] = troca;
				}

				troca = s_aux[coluna_atual + linhas];
//				cout << "I " << i << " s_aux[coluna_atual] " << s_aux[coluna_atual] << " s_aux[i] " << s_aux[i] << endl;
				s_aux[coluna_atual + linhas] = s_aux[i];
				s_aux[i] = troca;
				coluna_atual++;

//				for(j=0;j<linhas+colunas;j++)
//					cout << s_aux[j] << " ";
//				cout << endl;
			}
		}
	}

/*	cout << "Imprimindo a matriz de parcial" << endl;
	for (i=0;i<linhas;i++){
		for(j=0;j<colunas;j++)
			cout << nova[i][j] << " ";
		cout << endl;
	}
*/
	V.Solucao = s_aux;
	V.Matriz = nova;
	V.FO = calcular_FO(s_aux, clusters, V.Matriz);
	V.Movimento.DeLinha = deL;
	V.Movimento.ParaLinha = paraL;
	V.Movimento.DeColuna = deC;
	V.Movimento.ParaColuna = paraC;

	return V;
}


void imprimir_matriz(char **m){
	cout << "Imprimindo a matriz de parcial" << endl;
	for (int i=0;i<linhas;i++){
		for(int j=0;j<colunas;j++)
			cout << m[i][j] << " ";
		cout << endl;
	}
}

char * copiar_linha(char *l){
	int i;
	char *aux = (char *) calloc (colunas, sizeof(char));

	for(i = 0; i <= colunas; i++)
		aux[i] = l[i];

	return aux;
}

char ** trocar_colunas(char **s, int c1, int c2){
	char ** aux;
	int i, j;

	aux = (char **) calloc (linhas, sizeof(char *));
	for (i = 0; i < linhas; i++ )
		aux[i] = (char *) calloc (colunas, sizeof(char));

	for (i=0;i<linhas;i++){
		for(j=0;j<colunas;j++){
			if(j == c1)
				aux[i][j] = s[i][c2];
			else if(j == c2)
				aux[i][j] = s[i][c1];
			else
				aux[i][j] = s[i][j];
		}
	}

	return aux;
}

char ** copiar_matriz(char **s){
	char ** aux;
	int i, j;

	aux = (char **) calloc (linhas, sizeof(char *));

	/* aloca as colunas da matriz*/
	for (i = 0; i < linhas; i++ ) {
		aux[i] = (char *) calloc (colunas, sizeof(char));
	}

	for (i=0;i<linhas;i++)
		for (j=0;j<colunas;j++)
			aux[i][j] = s[i][j];

	return aux;
}

bool IsTabu(Vizinhanca V, Tabu* Lista){
	int i;
	for(i = 0; i < TamanhoTabu; i++){
//		cout << "verificando tabu " << i << endl;
		if(Lista[i].DeLinha != 0 && Lista[i].ParaLinha != 0 && Lista[i].DeColuna != 0 && Lista[i].ParaColuna != 0){
			if(Lista[i].DeLinha == V.Movimento.DeLinha && Lista[i].ParaLinha == V.Movimento.ParaLinha && Lista[i].DeColuna == V.Movimento.DeColuna && Lista[i].ParaColuna == V.Movimento.ParaColuna){
				return true;
			}
		}
	}
	return false;
}

Tabu * AtualizarListTabu(Tabu* Lista, Tabu Movimento){
	Tabu *L = (Tabu *) calloc (TamanhoTabu, sizeof(Tabu));
	int i;

	for(i = TamanhoTabu-1; i > 0; i--){
		L[i] = Lista[i-1];
	}
	L[0] = Movimento;
	return L;
}
